Operating system kernels provide several mechanisms to synchronize data structures in multi-threaded systems. Many of these mechanisms use a technique called spin waiting, where a thread or processor will spend time in a loop waiting for a particular event to occur before it continues execution. Spin waits are typically used in cases where wait times will be much less than the cost of re-scheduling threads or where the environment is such that the thread scheduler cannot run.
Examples of synchronization primitives that use this technique include, but are not limited to: spinlocks, queued spinlocks, reader/writer locks, and barriers. In general, well-designed operating systems will minimize the amount of time threads spend in regions of code that lead to these spin wait loops, since the time spent spin waiting is wasted time. At best, in the case of hyper-threading, some of a thread's resources are given to another hyper-thread, but such a thread is still blocked from making forward progress.
Furthermore, the assumption that spin waits will be performed only for short durations can be unintentionally broken when an operating system is running in a virtual machine environment. Consequently, the time spent spin waiting can increase greatly in virtual machine environments and can prevent a virtual machine from making forward progress.
Gang scheduling, in which all virtual processors of a virtual machine are scheduled in tandem, has been used in the past to avoid lock problems (resulting from spin waits). However, this approach often does not make efficient use of the physical system's processor(s). Gang scheduling can create un-schedulable holes where none of the sets of virtual processors from de-scheduled virtual machines will fit into given resources.
Furthermore, requiring all of the virtual processors from a virtual machine to run at the same time and for the same duration can result in cases where some of the virtual processors have no work to do but will run anyway. Both of these issues, long spin waits and gang scheduling, lead to under-utilization of system processors and significant throughput reductions. Thus, other techniques are needed in the art to solve the above described problems.